package xj.graph2d.graph;

import java.awt.geom.Dimension2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import xj.lang.CodeWriter;

import static xj.graph2d.graph.GraphUtilities.matchEdgeType;

public class AbstractSubgraph <NodeType extends GraphNode<EdgeType>, 
                               EdgeType extends GraphEdge<NodeType>>
  extends AbstractGraphComponent 
  implements Subgraph<NodeType, EdgeType>, 
	     GraphConstants {

  public AbstractSubgraph() {
    super(SUBGRAPH);
    nodeAttributes = new HashMap<String, Object>();
    edgeAttributes = new HashMap<String, Object>();
  }

  public AbstractSubgraph(String name) {
    super(SUBGRAPH, name);
    nodeAttributes = new HashMap<String, Object>();
    edgeAttributes = new HashMap<String, Object>();
  }

  public AbstractSubgraph(Subgraph subg) {
    super(SUBGRAPH, subg);
    nodeAttributes = new HashMap<String, Object>();
    edgeAttributes = new HashMap<String, Object>();
  }

  public AbstractSubgraph(Subgraph subg, String name) {
    super(SUBGRAPH, subg, name);
    nodeAttributes = new HashMap<String, Object>();
    edgeAttributes = new HashMap<String, Object>();
  }

  @Override
  public int getType() {
    return SUBGRAPH;
  }

  @Override
  public boolean isSubgraph() {
    return true;
  }

  /*
   * return true if the specified node is added; return false if the
   * specified node already exist.
   */
  public boolean addNode(NodeType node) {
    boolean result = false;
    if (node != null) {
      node.setSubgraph(this);
      String name = node.getName();
      if (name != null) {
	nodeMap.put(name, node);
      }
      result = nodeSet.add(node);
    }
    return result;
  }

  /*
   * return true if the specified node is removed; return false if the
   * specified node does not exist.
   */
  public boolean removeNode(NodeType node) {
    return removeNode(node, true);
  }

  public boolean removeNode(NodeType node, boolean disconnect) {
    if (node != null) {
      String name = node.getName();
      if (name != null) {
	nodeMap.remove(name);
      }

      if (disconnect) {
	Set<EdgeType> edges = node.leavingEdges();
	if (edges != null) {
	  for (Iterator<EdgeType> eiter1 = edges.iterator(); eiter1.hasNext();) {
	    EdgeType e1 = eiter1.next();
	    e1.setSource(null);
	  }
	  edges.clear();
	}

	edges = node.arrivingEdges();
	if (edges != null) {
	  for (Iterator<EdgeType> eiter2 = edges.iterator(); eiter2.hasNext();) {
	    EdgeType e2 = eiter2.next();
	    e2.setSource(null);
	  }
	  edges.clear();
	}
      }
      nodeSet.remove(node);
      return true;
    }
    return false;
  }

  public NodeType removeNode(String name) {
    return removeNode(name, true);
  }

  public NodeType removeNode(String name, boolean disconnect) {
    NodeType node = null;
    if (name != null) {
      node = findNodeByName(name);
      if (node != null) {
	removeNode(node, disconnect);
      }
    }
    return node;
  }

  /*
   * return true if the specified edge is removed; return false if the
   * specified edge does not exist.
   */
  public boolean addEdge(EdgeType edge) {
    return addEdge(edge, allowDuplicateEdges);
  }

  public boolean addEdge(EdgeType edge, boolean allowDuplicate) {
    if (edge != null) {
      edge.setSubgraph(this);
      String name = edge.getName();
      if (name != null) {
	edgeMap.put(name, edge);
      }

      NodeType src = edge.getSource();
      NodeType des = edge.getDestination();

      // System.out.println("AbstractSubgraph.addEdge(): src=" + src + "
      // des=" + des);

      if (allowDanglingEdges || (src != null && des != null)) {
	if (src != null && src.getSubgraph() == null && !containsNode(src)) {
	  addNode(src);
	}
	if (des != null && des.getSubgraph() == null && !containsNode(des)) {
	  addNode(des);
	}

	boolean duplicate = false;
	if (!allowDuplicate) {
	  for (Iterator<EdgeType> eiter = edgeSet.iterator(); eiter.hasNext();) {
	    EdgeType e = eiter.next();
	    if (e != null) {
	      NodeType esrc = e.getSource();
	      NodeType edes = e.getDestination();
	      if (src == esrc && des == edes) {
		duplicate = true;
		return false;
	      }
	    }
	  }
	}

	if (!duplicate) {
	  edge.setSubgraph(this);
	  if (src != null) {
	    Set<EdgeType> edges = src.leavingEdges();
	    if (edges != null) {
	      edges.add(edge);
	    }
	  }
	  if (des != null) {
	    Set<EdgeType> edges = des.arrivingEdges();
	    if (edges != null) {
	      edges.add(edge);
	    }
	  }
	  return edgeSet.add(edge);
	}
      }
    }
    return false;
  }

  /*
   * return true if the specified edge is removed; return false if the
   * specified edge does not exist.
   */
  public boolean removeEdge(EdgeType edge) {
    if (edge != null) {
      String name = edge.getName();
      if (name != null) {
	edgeMap.remove(name);
      }
      NodeType src = edge.getSource();
      NodeType des = edge.getDestination();
      if (src != null) {
	Set<EdgeType> edges = src.leavingEdges();
	if (edges != null) {
	  edges.remove(edge);
	}
	edge.setSource(null);
      }
      if (des != null) {
	Set<EdgeType> edges = des.arrivingEdges();
	if (edges != null) {
	  edges.remove(edge);
	}
	edge.setDestination(null);
      }
      return edgeSet.remove(edge);
    }
    return false;
  }

  public NodeType disconnectDestination(EdgeType edge) {
    if (allowDanglingEdges && edge != null) {
      NodeType des = edge.getDestination();
      if (des != null) {
	Set<EdgeType> edges = des.arrivingEdges();
	if (edges != null) {
	  edges.remove(edge);
	}
      }
      edge.setDestination(null);
      return des;
    }
    return null;
  }

  public NodeType disconnectSource(EdgeType edge) {
    if (allowDanglingEdges && edge != null) {
      NodeType src = edge.getSource();
      if (src != null) {
	Set<EdgeType> edges = src.leavingEdges();
	if (edges != null) {
	  edges.remove(edge);
	}
      }
      edge.setSource(null);
      return src;
    }
    return null;
  }

  public void connectDestination(EdgeType edge, NodeType node) {
    if (edge != null && node != null) {
      Set<EdgeType> edges = node.arrivingEdges();
      if (edges != null) {
	edges.add(edge);
      }
      edge.setDestination(node);
    }
  }

  public void connectSource(EdgeType edge, NodeType node) {
    if (edge != null && node != null) {
      Set<EdgeType> edges = node.leavingEdges();
      if (edges != null) {
	edges.add(edge);
      }
      edge.setSource(node);
    }
  }

  public EdgeType removeEdge(String name) {
    EdgeType edge = null;
    if (name != null) {
      edge = findEdgeByName(name);
      if (edge != null) {
	removeEdge(edge);
      }
    }
    return edge;
  }

  public void reverseEdgeDirection(EdgeType edge) { 
    if (edge != null) {
      NodeType src = disconnectSource(edge);
      NodeType des = disconnectDestination(edge);
      if (src != null) { 
	connectDestination(edge, src); 
      }
      if (des != null) { 
	connectSource(edge, des); 
      }
    }
  }


  public void moveEdgeToSubgraph(EdgeType edge, Subgraph<NodeType, EdgeType> subg) {
    if (edge != null && 
	subg != null && 
	subg != this) { 
      String name = edge.getName();
      if (name != null) {
	edgeMap.remove(name);
      }
      edgeSet.remove(edge);

      subg.addEdge(edge);
    }
  }

  public void removeAllNodes() {
    nodeSet.clear();
    edgeSet.clear();
  }

  public int getNumberOfNodes() {
    return nodeSet.size();
  }

  public int getNumberOfEdges() {
    return edgeSet.size();
  }

  public boolean isEmpty() {
    return (nodeSet.size() == 0 && edgeSet.size() == 0);
  }

  public boolean addSubgraph(Subgraph<NodeType, EdgeType> subg) {
    if (subg != null) {
      subg.setSubgraph(this);
      String name = subg.getName();
      if (name != null) {
	subgraphMap.put(name, subg);
      }
      return subgraphSet.add(subg);
    }
    return false;
  }

  public boolean removeSubgraph(Subgraph<NodeType, EdgeType> subg) {
    if (subg != null) {
      String name = subg.getName();
      if (name != null) {
	subgraphMap.remove(name);
      }
      return subgraphSet.remove(subg);
    }
    return false;
  }

  public boolean removeSubgraph(String name) {
    if (name != null) {
      Subgraph subg = findSubgraphByName(name);
      if (subg != null) {
	removeSubgraph(subg);
      }
    }
    return false;
  }

  public boolean containsNode(NodeType node) {
    if (node != null) {
      return nodeSet.contains(node);
    }
    return false;
  }

  public boolean containsEdge(EdgeType edge) {
    if (edge != null) {
      return edgeSet.contains(edge);
    }
    return false;
  }

  public Set<NodeType> allSubnodes() {
    return getAllSubnodes(this, null);
  }

  protected static <N extends GraphNode<E>, E extends GraphEdge<N>> 
    Set<N> getAllSubnodes(Subgraph<N, E> graph, Set<N> set) {
    if (graph != null) {
      if (set == null) {
	set = new HashSet<N>();
      }
      Iterator<N> iter = graph.nodes();
      if (iter != null) {
	while (iter.hasNext()) {
	  N n = iter.next();
	  if (n instanceof Subgraph) {
	    Subgraph<N, E> sg = (Subgraph<N, E>) n;
	    getAllSubnodes(sg, set);
	  }
	}
      }
    }
    return set;
  }

  public boolean containsSubnode(NodeType node) {
    return containsSubnode(this, node);
  }

  protected static <N extends GraphNode<E>, E extends GraphEdge<N>> 
    boolean containsSubnode(Subgraph<N, E> graph, N node) {
    if (graph != null && node != null) {
      Iterator<N> iter = graph.nodes();
      if (iter != null) {
	while (iter.hasNext()) {
	  N n = iter.next();
	  if (n == node) {
	    return true;
	  }
	  if (n instanceof Subgraph) {
	    Subgraph<N, E> sg = (Subgraph<N, E>) n;
	    boolean b = containsSubnode(sg, node);
	    if (b) {
	      return true;
	    }
	  }
	}
      }
    }
    return false;
  }

  /**
   * Searches current subgraph for the node matching the supplied name.
   * 
   * @param name
   *                the name of the node to be found.
   * @return the Node matching the name or null, if there is no match.
   */
  public NodeType findNodeByName(String name) {
    return findNodeByName(name, false);
  }

  public NodeType findNodeByName(String name, boolean deep) {
    if (name != null) {
      return nodeMap.get(name);
    }
    if (deep && subgraphSet != null) {
      Iterator<Subgraph<NodeType, EdgeType>> iter = subgraphSet.iterator();
      while (iter.hasNext()) {
	Subgraph<NodeType, EdgeType> subg = iter.next();
	NodeType node = subg.findNodeByName(name, true);
	if (node != null) {
	  return node;
	}
      }
    }
    return null;
  }

  /**
   * Searches current subgraph for the edge matching the supplied name.
   * 
   * @param name
   *                the name of the edge to be found.
   * @return the Edge matching the name or null, if there is no match.
   */
  public EdgeType findEdgeByName(String name) {
    return findEdgeByName(name, false);
  }

  public EdgeType findEdgeByName(String name, boolean deep) {
    if (name != null) {
      return edgeMap.get(name);
    }
    if (deep && subgraphSet != null) {
      Iterator<Subgraph<NodeType, EdgeType>> iter = subgraphSet.iterator();
      while (iter.hasNext()) {
	Subgraph<NodeType, EdgeType> subg = iter.next();
	EdgeType edge = subg.findEdgeByName(name, true);
	if (edge != null) {
	  return edge;
	}
      }
    }
    return null;
  }

  /**
   * Searches current subgraph for the subgraph matching the supplied
   * name.
   * 
   * @param name
   *                the name of the subgraph to be found.
   * @return the Subgraph matching the name or null, if there is no match.
   */
  public Subgraph findSubgraphByName(String name) {
    return findSubgraphByName(name, false);
  }

  public Subgraph<NodeType, EdgeType> findSubgraphByName(String name, boolean deep) {
    if (name != null) {
      return subgraphMap.get(name);
    }
    if (deep && subgraphSet != null) {
      Iterator<Subgraph<NodeType, EdgeType>> iter = subgraphSet.iterator();
      while (iter.hasNext()) {
	Subgraph<NodeType, EdgeType> subg = iter.next();
	Subgraph<NodeType, EdgeType> sg = subg.findSubgraphByName(name, true);
	if (sg != null) {
	  return sg;
	}
      }
    }
    return null;
  }

  public Iterator<NodeType> nodes() {
    return nodeSet.iterator();
  }

  public Iterator<EdgeType> edges() {
    return edgeSet.iterator();
  }

  public Iterator<Subgraph<NodeType, EdgeType>> subgraphs() {
    return subgraphSet.iterator();
  }

  public Set<NodeType> getNodeSet() {
    return nodeSet;
  }

  public Set<EdgeType> getEdgeSet() {
    return edgeSet;
  }

  public Set<Subgraph<NodeType, EdgeType>> getSubgraphSet() {
    return subgraphSet;
  }

  public Set<EdgeType> leavingEdges(NodeType node) {
    if (node != null) {
      return node.leavingEdges();
    }
    return null;
  }

  public Set<EdgeType> leavingEdges(NodeType node, int edgeType) {
    Set<EdgeType> result = null;
    if (node != null) {
      Set<EdgeType> edges = node.leavingEdges();
      if (edges != null) {
	result = new HashSet<EdgeType>();
	Iterator<EdgeType> iter = edges.iterator();
	while (iter.hasNext()) {
	  EdgeType e = iter.next();
	  if (matchEdgeType(edgeType, e)) {
	    result.add(e);
	  }
	}
      }
    }
    return result;
  }

  public Set<EdgeType> arrivingEdges(NodeType node) {
    if (node != null) {
      return node.arrivingEdges();
    }
    return null;
  }

  public Set<EdgeType> arrivingEdges(NodeType node, int edgeType) {
    Set<EdgeType> result = null;
    if (node != null) {
      Set<EdgeType> edges = node.arrivingEdges();
      if (edges != null) {
	result = new HashSet<EdgeType>();
	Iterator<EdgeType> iter = edges.iterator();
	while (iter.hasNext()) {
	  EdgeType e = iter.next();
	  if (matchEdgeType(edgeType, e)) {
	    result.add(e);
	  }
	}
      }
    }
    return result;
  }

  public int getDegree(NodeType node) {
    if (node != null) {
      return node.getDegree();
    }
    return 0;
  }

  public int getInDegree(NodeType node) {
    if (node != null) {
      return node.getInDegree();
    }
    return 0;
  }

  public int getOutDegree(NodeType node) {
    if (node != null) {
      return node.getOutDegree();
    }
    return 0;
  }

  public NodeType searchNode(Point2D p) {
    NodeType result = null;
    for (Iterator<NodeType> iter = nodeSet.iterator(); iter.hasNext();) {
      NodeType node = iter.next();
      if (node != null) {
	int pos = node.isInside(p);
	if (pos != PointOutside) {
	  result = node;
	  break;
	}
      }
    }
    return result;
  }

  public void move(double dx, double dy) {
    for (Iterator<NodeType> iter = nodeSet.iterator(); iter.hasNext();) {
      NodeType node = iter.next();
      node.move(dx, dy);
    }
  }

  public Rectangle2D getBounds() {
    Rectangle2D rect = null;
    Iterator<NodeType> niter = nodes();
    while (niter.hasNext()) {
      NodeType node = niter.next();
      if (node != null) {
	Point2D p = node.getULCorner();
	Dimension2D d = node.getSize();
	Rectangle2D r = new Rectangle2D.Float((float) p.getX(), (float) p
					      .getY(), (float) d.getWidth(), (float) d.getHeight());
	if (rect == null) {
	  rect = r;
	} else {
	  Rectangle2D.union(rect, r, rect);
	  // rect = rect.union(r);
	}
      }
    }

    if (rect != null) {
      return rect;
    } else {
      return new Rectangle2D.Float(0, 0, 0, 0);
    }
  }

  public void setNodeAttribute(String name, Object value) {
    if (name != null && nodeAttributes != null) {
      nodeAttributes.put(name, value);
    }
  }

  public void removeNodeAttribute(String name) {
    if (name != null && nodeAttributes != null) {
      nodeAttributes.remove(name);
    }
  }

  public Object getNodeAttribute(String key) {
    if (key != null && nodeAttributes != null) {
      return nodeAttributes.get(key);
    }
    return null;
  }

  public void setEdgeAttribute(String name, Object value) {
    if (name != null && edgeAttributes != null) {
      edgeAttributes.put(name, value);
    }
  }

  public void removeEdgeAttribute(String name) {
    if (name != null && edgeAttributes != null) {
      edgeAttributes.remove(name);
    }
  }

  public Object getEdgeAttribute(String key) {
    if (key != null && edgeAttributes != null) {
      return edgeAttributes.get(key);
    }
    return null;
  }

  /**
   * Prints an ascii description of each graph element to the supplied
   * stream.
   * 
   * @param output
   *                the OutputStream for writing the graph description.
   */
  public void printSubgraph(PrintWriter out) {
    Graph graph = getGraph();
    String indent = new String(graph.getIndent());

    if (getSubgraph() == null) {
      // this subgraph is the root
      out.println(indent + (graph.isStrict() ? "strict " : "") + 
		  (graph.isDirected() ? "digraph" : "graph") + " " + 
		  graph.toString() + " {");
    } else if (getName().startsWith(ANONYMOUS_PREFIX)) {
      out.println(indent + "{");
    } else {
      out.println(indent + "subgraph " + this.toString() + " {");
    }

    graph.incrementIndent();

    //printDflt(out, SUBGRAPH);
    //printDflt(out, NODE);
    //printDflt(out, EDGE);

    if (nodeSet != null && !nodeSet.isEmpty()) {
      Iterator<NodeType> iter = nodes();
      while (iter.hasNext()) {
	(iter.next()).printNode(out);
      }
    }
    if (edgeSet != null && !edgeSet.isEmpty()) {
      Iterator<EdgeType> iter = edges();
      while (iter.hasNext()) {
	(iter.next()).printEdge(out);
      }
    }
    if (subgraphSet != null && !subgraphSet.isEmpty()) {
      Iterator<Subgraph<NodeType, EdgeType>> iter = subgraphs();
      while (iter.hasNext()) {
	iter.next().printSubgraph(out);
      }
    }

    graph.decrementIndent();

    out.println(indent + "}");
  }

  private String makePad(int level) {
    String s = "";
    if (level > 0) {
      for (int i = 0; i < level; i++) {
	s += ' ';
      }
    }
    return s;
  }

  public void printSubgraph(int level) {
    String pad = makePad(level);
    String nstr = "V = {";
    String estr = "E = {";
    boolean first = true;
    Iterator<NodeType> niter = nodes();
    while (niter.hasNext()) {
      if (first) {
	first = false;
      } else {
	nstr += ", ";
      }
      NodeType n = niter.next();
      nstr += n.getId();
      // nstr += n.getName();
    }

    first = true;
    Iterator<EdgeType> eiter = edges();
    while (eiter.hasNext()) {
      if (first) {
	first = false;
      } else {
	estr += ", ";
      }
      EdgeType e = eiter.next();
      estr += (e.getId() + "=" + e.getEdgeString());
      // estr += (e.getName() + "=" + e.getEdgeString());
    }
    System.out.println(pad + nstr + "}");
    System.out.println(pad + estr + "}");

    niter = nodes();
    while (niter.hasNext()) {
      NodeType n = niter.next();
      nstr = (n.getId() + ": out ");
      Set<EdgeType> edgeSet = leavingEdges(n);
      Iterator<EdgeType> edges;
      if (edgeSet != null) {
	nstr += "[";
	edges = edgeSet.iterator();
	first = true;
	while (edges.hasNext()) {
	  if (first) {
	    first = false;
	  } else {
	    nstr += ",";
	  }
	  EdgeType edge = edges.next();
	  nstr += edge.getId();
	  // nstr += edge.getName();
	}
	nstr += "] ";
      } else {
	nstr += "- ";
      }

      nstr += "in ";
      edgeSet = arrivingEdges(n);
      if (edgeSet != null) {
	nstr += "[";
	edges = edgeSet.iterator();
	first = true;
	while (edges.hasNext()) {
	  if (first) {
	    first = false;
	  } else {
	    nstr += ",";
	  }
	  EdgeType edge = edges.next();
	  nstr += edge.getId();
	  // nstr += edge.getName();
	}
	nstr += "]";
      } else {
	nstr += "-";
      }

      Subgraph parent = n.getSubgraph();
      nstr += (" parent=" + (parent == null ? "null" : parent.getId()));

      if (n instanceof HyperGraphNode) {
	nstr += " hypernode";
      }

      System.out.println(pad + nstr);

      if (n instanceof HyperGraphNode) {
	HyperGraphNode<NodeType, EdgeType> hn = (HyperGraphNode<NodeType, EdgeType>) n;
	hn.printSubgraph(level + 1);
      }
    }

    Iterator<Subgraph<NodeType, EdgeType>> siter = subgraphs();
    while (siter.hasNext()) {
      Subgraph<NodeType, EdgeType> sg = siter.next();
      System.out.println(pad + "subgraph " + sg.getId());
      sg.printSubgraph(level + 1);
    }
  }

  public static String getPrefixedName(String name, String namespacePrefix) {
    if (namespacePrefix != null && namespacePrefix.length() > 0) {
      return namespacePrefix + ":" + name;
    } else {
      return name;
    }
  }

  public void writeSubgraphXML(CodeWriter out, String namespacePrefix) {
    if (out != null) {
      String nodename = getPrefixedName("Subgraph", namespacePrefix);
      if (isEmpty()) {
	out.println("<" + nodename + " id=\"" + getId() + "\"/>");
      } else {
	out.indentInc();
	out.println("<" + nodename + " id=\"" + getId() + "\">");

	String nodeElement = getPrefixedName("Node", namespacePrefix);
	String edgeElement = getPrefixedName("Edge", namespacePrefix);

	// write nodes
	String nodes = getPrefixedName("Nodes", namespacePrefix);
	if (getNumberOfNodes() > 0) {
	  out.indentInc();
	  out.println("<" + nodes + ">");
	  Iterator<NodeType> niter = nodes();
	  while (niter.hasNext()) {
	    NodeType n = niter.next();
	    String id = n.getId();
	    if (id == null) {
	      continue;
	    }

	    HyperGraphNode<NodeType, EdgeType> hn = null;
	    if (n instanceof HyperGraphNode) {
	      hn = (HyperGraphNode<NodeType, EdgeType>) n;
	    }
	    if (getDegree(n) == 0 && 
		(hn == null || hn != null && hn.isEmpty())) {
	      out.println("<" + nodeElement + " id=\"" + id + "\"/>");
	    } else {
	      out.indentInc();
	      out.println("<" + nodeElement + " id=\"" + id + "\">");

	      // write out-going edges
	      String leavingEdges = getPrefixedName("OutEdges", namespacePrefix);
	      Set<EdgeType> edgeSet = leavingEdges(n);
	      Iterator<EdgeType> edges;
	      if (edgeSet != null && edgeSet.size() > 0) {
		edges = edgeSet.iterator();
		out.indentInc();
		out.println("<" + leavingEdges + ">");
		while (edges.hasNext()) {
		  EdgeType e = edges.next();
		  if (e != null) {
		    out.println("<" + edgeElement + " refid=\"" + e.getId()
				+ "\"/>");
		  }
		}
		out.thisIndentDec();
		out.println("</" + leavingEdges + ">");
		// } else {
		// out.println("<" + leavingEdges + "/>");
	      }

	      // write in-coming edges
	      String arrivingEdges = getPrefixedName("InEdges", namespacePrefix);
	      edgeSet = arrivingEdges(n);
	      if (edgeSet != null && edgeSet.size() > 0) {
		edges = edgeSet.iterator();
		out.indentInc();
		out.println("<" + arrivingEdges + ">");
		while (edges.hasNext()) {
		  EdgeType e = edges.next();
		  if (e != null) {
		    out.println("<" + edgeElement + " refid=\"" + e.getId()
				+ "\"/>");
		  }
		}
		out.thisIndentDec();
		out.println("</" + arrivingEdges + ">");
		// } else {
		// out.println("<" + arrivingEdges + "/>");
	      }

	      // write hypernode subelements
	      if (hn != null && !hn.isEmpty()) {
		hn.writeSubgraphXML(out, namespacePrefix);
	      }

	      out.thisIndentDec();
	      out.println("</" + nodeElement + ">");
	    }
	  }
	  out.thisIndentDec();
	  out.println("</" + nodes + ">");
	}

	// write edges
	if (getNumberOfEdges() > 0) {
	  out.indentInc();
	  String edges = getPrefixedName("Edges", namespacePrefix);
	  out.println("<" + edges + ">");
	  Iterator<EdgeType> eiter = edges();
	  while (eiter.hasNext()) {
	    EdgeType e = eiter.next();
	    String id = e.getId();
	    if (id == null) {
	      continue;
	    }

	    if (e != null) {
	      NodeType src = e.getSource();
	      NodeType des = e.getDestination();
	      out.print("<" + edgeElement + " id=\"" + id);
	      if (src != null) {
		out.print("\" src=\"" + src.getId());
	      } else {
		out.print("\" src=\"-");
	      }
	      if (des != null) {
		out.print("\" des=\"" + des.getId());
	      } else {
		out.print("\" des=\"-");
	      }
	      out.println("\"/>");
	    }
	  }
	  out.thisIndentDec();
	  out.println("</" + edges + ">");
	}

	// write subgraph
	if (subgraphSet.size() > 0) {
	  Iterator<Subgraph<NodeType, EdgeType>> siter = subgraphs();
	  while (siter.hasNext()) {
	    Subgraph<NodeType, EdgeType> sg = siter.next();
	    sg.writeSubgraphXML(out, namespacePrefix);
	  }
	}

	out.thisIndentDec();
	out.println("</" + nodename + ">");
      }
    }
  }

  public void buildSubgraphFromXML(org.w3c.dom.Node node, 
				   String uri0,
				   Map<String, Object> compShapeMap) {
    // System.out.println("AbstractSubgraph.buildSubgraphFromXML(): " +
    // (node != null ? node.getLocalName() : "null"));

    if (node != null && 
	compShapeMap != null) {

      org.w3c.dom.NodeList nodes = node.getChildNodes();
      if (nodes != null) {
	int m = nodes.getLength();
	for (int j = 0; j < m; j++) {
	  org.w3c.dom.Node gnode = nodes.item(j);
	  String uri = gnode.getNamespaceURI();
	  if (gnode.getNodeType() == org.w3c.dom.Node.ELEMENT_NODE && 
	      (uri0 == null || uri0.equals(uri))) {
	    if ("Nodes".equals(gnode.getLocalName())) {
	      org.w3c.dom.NodeList nodelist = gnode.getChildNodes();
	      if (nodelist != null) {
		int nn = nodelist.getLength();
		for (int i = 0; i < nn; i++) {
		  org.w3c.dom.Node nnode = nodelist.item(i);
		  uri = nnode.getNamespaceURI();
		  if (nnode.getNodeType() == org.w3c.dom.Node.ELEMENT_NODE && 
		      (uri0 == null || uri0.equals(uri))) {
		    if ("Node".equals(nnode.getLocalName())) {
		      org.w3c.dom.Element e = (org.w3c.dom.Element) nnode;
		      String nodeid = e.getAttribute("id");
		      Object o = compShapeMap.get(nodeid);
		      NodeType graphnode = null;
		      if (o instanceof GraphNode) {
			graphnode = (NodeType) o;
			addNode(graphnode);
		      }

		      org.w3c.dom.NodeList nodechildren = nnode.getChildNodes();
		      if (nodechildren != null) {
			int nnc = nodechildren.getLength();
			for (int k = 0; k < nnc; k++) {
			  org.w3c.dom.Node nchild = nodechildren.item(k);
			  uri = nchild.getNamespaceURI();
			  if (nchild.getNodeType() == org.w3c.dom.Node.ELEMENT_NODE && 
			      (uri0 == null || uri0.equals(uri))) {
			    // handling hypernode
			    if ("Subgraph".equals(nchild.getLocalName())) {
			      if (graphnode instanceof Subgraph) {
				Subgraph<NodeType, EdgeType> subg = 
				  (Subgraph<NodeType, EdgeType>) graphnode;
				subg.buildSubgraphFromXML(nchild, uri0,
							  compShapeMap);

				org.w3c.dom.Element e1 = (org.w3c.dom.Element) nchild;
				String subid = e1.getAttribute("id");
				subg.setId(subid);
			      }
			    }
			  }
			}
		      }
		    }
		  }
		}
	      }
	    } else if ("Edges".equals(gnode.getLocalName())) {
	      org.w3c.dom.NodeList edgelist = gnode.getChildNodes();
	      if (edgelist != null) {
		int ne = edgelist.getLength();
		for (int i = 0; i < ne; i++) {
		  org.w3c.dom.Node enode = edgelist.item(i);
		  uri = enode.getNamespaceURI();
		  if (enode.getNodeType() == org.w3c.dom.Node.ELEMENT_NODE
		      && (uri0 == null || uri0.equals(uri))) {
		    if ("Edge".equals(enode.getLocalName())) {
		      org.w3c.dom.Element e = (org.w3c.dom.Element) enode;
		      String edgeid = e.getAttribute("id");
		      Object o = compShapeMap.get(edgeid);
		      if (o instanceof GraphEdge) {
			EdgeType edge = (EdgeType) o;
			NodeType srcNode = null;
			NodeType desNode = null;
			String srcid = e.getAttribute("src");
			o = compShapeMap.get(srcid);
			if (o instanceof GraphNode) {
			  srcNode = (NodeType) o;
			  edge.setSource(srcNode);
			}
			String desid = e.getAttribute("des");
			o = compShapeMap.get(desid);
			if (o instanceof GraphNode) {
			  desNode = (NodeType) o;
			  edge.setDestination(desNode);
			}
			addEdge(edge);
		      }
		    }
		  }
		}
	      }
	    } else if ("Subgraph".equals(gnode.getLocalName())) {
	      if (gnode.getNodeType() == org.w3c.dom.Node.ELEMENT_NODE) {
		org.w3c.dom.Element e = (org.w3c.dom.Element) gnode;
		String subgid = e.getAttribute("id");
		Object o = compShapeMap.get(subgid);
		if (o instanceof Subgraph) {
		  Subgraph subg = (Subgraph) o;
		  subg.buildSubgraphFromXML(gnode, uri0, compShapeMap);
		}
	      }
	    }
	  }
	}
      }
    }
  }


  public boolean isAllowDanglingEdges() {
    return allowDanglingEdges;
  }

  public void setAllowDanglingEdges(boolean allowDanglingEdges) {
    this.allowDanglingEdges = allowDanglingEdges;
  }

  public boolean isAllowDuplicateEdges() {
    return allowDuplicateEdges;
  }

  public void setAllowDuplicateEdges(boolean allowDuplicateEdges) {
    this.allowDuplicateEdges = allowDuplicateEdges;
  }

  protected String getDefaultNamePrefix() {
    if (prefix != null) {
      return prefix + "g";
    } else {
      return "g";
    }
  }

  protected static int _id = 1;

  protected int getNextId() {
    return _id++;
  }

  protected boolean allowDanglingEdges = false;
  protected boolean allowDuplicateEdges = false;

  // default node attributes
  protected Map<String, Object> nodeAttributes = null;

  // default edge attributes
  protected Map<String, Object> edgeAttributes = null;

  protected Set<NodeType> nodeSet = new HashSet<NodeType>();

  protected Set<EdgeType> edgeSet = new HashSet<EdgeType>();

  protected Set<Subgraph<NodeType, EdgeType>> subgraphSet = 
    new HashSet<Subgraph<NodeType, EdgeType>>();

  protected Map<String, NodeType> nodeMap = new HashMap<String, NodeType>();

  protected Map<String, EdgeType> edgeMap = new HashMap<String, EdgeType>();

  protected Map<String, Subgraph<NodeType, EdgeType>> subgraphMap = 
    new HashMap<String, Subgraph<NodeType, EdgeType>>();

}
